// Tag: SegmentTree in Value
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define lowbit(x) (x & -x)
typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 1e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, q;
ll a[N], hash[N], ans[N * 3];

struct query {
  int l, r, id;
} Q[N * 3];

struct BinaryIndexedArray {
  ll val[N];

  inline void init() { memset(val, (int)inf, sizeof(val)); }

  void modify(int x, ll v) {
    while (x) val[x] = std::min(val[x], v), x -= lowbit(x);
  }

  ll query(ll x) {
    ll res = inf;
    while (x <= n) res = std::min(res, val[x]), x += lowbit(x);
    return res;
  }

} bit;

struct SegmentTree {
  ll val[N << 2];
  inline void pushup(int x) { val[x] = std::max(val[x << 1], val[x << 1 | 1]); }

  void modify(int x, int l, int r, int p, ll v) {
    if (l == r) { return val[x] = v, void(); }
    int mid = (l + r) >> 1;
    if (p <= mid) modify(x << 1, l, mid, p, v);
    else
      modify(x << 1 | 1, mid + 1, r, p, v);
    pushup(x);
  }

  ll query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) return val[x];
    int mid = (l + r) >> 1;
    ll res = 0;
    if (L <= mid) res = std::max(res, query(x << 1, l, mid, L, R));
    if (mid < R) res = std::max(res, query(x << 1 | 1, mid + 1, r, L, R));
    return res;
  }
} seg;

inline int find(ll x) {
  int l = 0, r = *hash;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (hash[mid] <= x) l = mid;
    else
      r = mid - 1;
  }
  return l;
}

signed main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("shopping.in", "r", stdin);
  freopen("shopping.out", "w", stdout);
#endif
#endif

  read(n);
  for (int i = 1; i <= n; i++) hash[i] = read(a[i]);
  std::sort(hash + 1, hash + n + 1);
  *hash = std::unique(hash + 1, hash + n + 1) - hash - 1;
  for (int i = 1; i <= n; i++)
    a[i] = std::lower_bound(hash + 1, hash + *hash + 1, a[i]) - hash;
  read(q);
  for (int i = 1; i <= q; i++) read(Q[i].l), read(Q[i].r), Q[i].id = i;
  std::sort(Q + 1, Q + q + 1,
            [](const query &lhs, const query &rhs) { return lhs.r < rhs.r; });
  bit.init();
  for (int i = 1, pos = 1; i <= n; i++) {
    if (i != 1) {
      int sj = *hash, xj = a[i], tmp = seg.query(1, 1, *hash, xj, sj);
      while (tmp) {
        bit.modify(tmp, hash[a[tmp]] - hash[a[i]]);
        sj = find((hash[a[tmp]] + hash[a[i]]) >> 1);
        if (!sj) break;
        if (sj >= a[tmp]) sj = a[tmp] - 1;
        if (xj > sj) break;
        tmp = seg.query(1, 1, *hash, xj, sj);
      }
      sj = a[i], xj = 1;
      tmp = seg.query(1, 1, *hash, xj, sj);
      while (tmp) {
        bit.modify(tmp, hash[a[i]] - hash[a[tmp]]);
        xj = find((hash[a[tmp]] + hash[a[i]]) >> 1);
        if (!xj) break;
        if (xj <= a[tmp]) xj = a[tmp] + 1;
        if (xj > sj) break;
        tmp = seg.query(1, 1, *hash, xj, sj);
      }
      while (Q[pos].r == i) {
        ans[Q[pos].id] = bit.query(Q[pos].l);
        ++pos;
      }
    }
    seg.modify(1, 1, *hash, a[i], i);
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}